home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Language/OS - Multiplatform Resource Library
/
LANGUAGE OS.iso
/
cpp_libs
/
intrvews
/
tech.txt
< prev
next >
Wrap
Text File
|
1993-07-24
|
34KB
|
718 lines
The following Technical Reports are available from the International
Computer Science Institute via anonymous FTP from icsi-ftp.Berkeley.EDU.
They are located in ~ftp/pub/techreports and are all compressed, postscript
files. If you experience difficulties, send mail to ftp-info@icsi.Berkeley.EDU.
-------------------------------------------------------------------------------
tr-89-032.ps.Z
A Connectionist Model of Unification
Andreas Stolcke
TR-89-032
May 1989
A general approach to encode and unify recursively
nested feature structures in connectionist networks is
described. The unification algorithm implemented by
the net is based on iterative coarsening of equivalence
classes of graph nodes. This method allows the
reformulation of unification as a constraint
satisfaction problem and enables the connectionist
implementation to take full advantage of the potential
parallelism inherent in unification, resulting in
sublinear time complexity. Moreover, the method is
able to process any number of feature structures in
parallel, searching for possible unifications and
making decisions among mutually exclusive unifications
where necessary.
Keywords and phrases. Unification, constraint
satisfaction, connectionism, feature structures.
-------------------------------------------------------------------------------
tr-90-009.ps.Z
Miniature Language Acquisition: A touchstone for cognitive science
Jerome A. Feldman, George Lakoff, Andreas Stolcke,
and Susan Hollbach Weber
TR-90-009
March 1990 (revised April 1990)
Cognitive Science, whose genesis was interdisciplinary,
shows signs of reverting to a disjoint collection of
fields. This paper presents a compact, theory-free
task that inherently requires an integrated solution.
The basic problem is learning a subset of an arbitrary
natural language from picture-sentence pairs. We
describe a very specific instance of this task and show
how it presents fundamental (but not impossible)
challenges to several areas of cognitive science
including vision, language, inference and learning.
-------------------------------------------------------------------------------
tr-90-010.ps.Z
L0: A Testbed for Miniature Language Acquisition
Susan Hollbach Weber and Andreas Stolcke
TR-90-010
July 1990
L0 constitutes a recent effort in Cognitive Science to
build a natural language acquisition system for a
limited visual domain. As a preparatory step towards
addressing the issue of learning in this domain, we
have built a set of tools for rapid prototyping and
experimentation in the areas of language processing,
image processing, and knowledge representation. The
special focus of our work was the integration of these
different components into a flexible system which would
allow us to better understand the domain given by L0
and experiment with alternative approaches to the
problems it poses.
-------------------------------------------------------------------------------
tr-90-011.ps.Z
A Network for Extracting the Locations of Point Clusters
Using Selective Attention
Subutai Ahmad and Stephen Omohundro
ahmad@icsi.berkeley.edu and om@icsi.berkeley.edu
TR 90-011
This report explores the problem of dynamically
computing visual relations in connectionist systems.
It concentrates on the task of learning whether
three clumps of points in a 256x256 image form an
equilateral triangle. We argue that feed-forward
networks for solving this task would not scale well
to images of this size. One reason for this is that
local information does not contribute to the
solution: it is necessary to compute relational
information such as the distances between points.
Our solution implements a mechanism for dynamically
extracting the locations of the point clusters. It
consists of an efficient focus of attention
mechanism and a cluster detection scheme. The focus
of attention mechanism allows the system to select
any circular portion of the image in constant time.
The cluster detector directs the focus of attention
to clusters in the image. These two mechanisms are
used to sequentially extract the relevant
coordinates. With this new representation
(locations of the points) very few training examples
are required to learn the correct function. The
resulting network is also very compact: the number
of required weights is proportional to the number of
input pixels.
-------------------------------------------------------------------------------
tr-90-015.ps.Z
Learning Feature-based Semantics with Simple Recurrent Networks
Andreas Stolcke
TR-90-015
April 1990
The paper investigates the possibilities for using
simple recurrent networks as transducers which map
sequential natural language input into non-sequential
feature-based semantics. The networks perform well on
sentences containing a single main predicate (encoded
by transitive verbs or prepositions) applied to
multiple-feature objects (encoded as noun-phrases with
adjectival modifiers), and shows robustness against
ungrammatical inputs. A second set of experiments
deals with sentences containing embedded structures.
Here the network is able to process multiple levels of
sentence-final embeddings but only one level of
center-embedding. This turns out to be a consequence
of the network's inability to retain information that
is not reflected in the outputs over intermediate
phases of processing. Two extensions to Elman's
\shortcite{Elman:88} original recurrent network
architecture are introduced.
-------------------------------------------------------------------------------
tr-91-030.ps.Z
Probability estimation by feed-forward networks in continuous speech
recognition
Steve Renals, Nelson Morgan and Herve Bourlard
TR-91-030
August 1991
We review the use of feed-forward networks as estimators of
probability densities in hidden Markov modelling. In this
paper we are mostly concerned with radial basis functions
(RBF) networks. We note the isomorphism of RBF networks to
tied mixture density estimators; additionally we note that
RBF networks are trained to estimate posteriors rather than
the likelihoods estimated by tied mixture density
estimators. We show how the neural network training should
be modified to resolve this mismatch. We also discuss
problems with discriminative training, particularly the
problem of dealing with unlabelled training data and the
mismatch between model and data priors.
-------------------------------------------------------------------------------
tr-91-031.ps.Z
pSather monitors: Design, Tutorial, Rationale and Implementation
Jerome A. Feldman, Chu-Cheow Lim and Franco Mazzanti
TR-91-031
September 1989
Sather is a new object-oriented programming language
under development at the International Computer
Science Institute. The initial beta test release of
the language was in June, 1991. From the outset, one
goal of the Sather project has been the incorporation
of constructs to support parallel programming.
pSather is a parallel extension of Sather aimed at
shared memory parallel architectures. A prototype of
the language is currently being implemented on a
Sequent Symmetry and on SUN Sparc-Stations.
pSather monitors are one of the basic new features
introduced in the language to deal with parallelism.
The current design is presented and discussed in
detail.
-------------------------------------------------------------------------------
tr-91-032.ps.Z
GAL: Networks that grow when they learn and shrink when they forget
Ethem Alpaydin
TR 91-032
Learning when limited to modification of some
parameters has a limited scope; the capability to
modify the system structure is also needed to get a
wider range of the learnable. In the case of
artificial neural networks, learning by iterative
adjustment of synaptic weights can only succeed if
the network designer predefines an appropriate network
structure, i.e., number of hidden layers, units,
and the size and shape of their receptive and
projective fields. This paper advocates the view
that the network structure should not, as usually
done, be determined by trial-and-error but should be
computed by the learning algorithm. Incremental
learning algorithms can modify the network structure
by addition and/or removal of units and/or links. A
survey of current connectionist literature is given on
this line of thought. ``Grow and Learn'' (GAL) is a
new algorithm that learns an association at one-shot
due to being incremental and using a local
representation. During the so-called ``sleep''
phase, units that were previously stored but which
are no longer necessary due to recent modifications
are removed to minimize network complexity.
The incrementally constructed network can later
be finetuned off-line to improve performance.
Another method proposed that greatly increases
recognition accuracy is to train a number of
networks and vote over their responses. The
algorithm and its variants are tested on
recognition of handwritten numerals and seem
promising especially in terms of learning speed.
This makes the algorithm attractive for on-line
learning tasks, e.g., in robotics. The
biological plausibility of incremental learning is
also discussed briefly.
Keywords
Incremental learning, supervised learning,
classificomion, pruning, destructive methods, growth,
constructive methods, nearest neighbor.
-------------------------------------------------------------------------------
tr-91-034.ps.Z
Sather Language Design and Performance Evaluation
Chu-Cheow Lim and Andreas Stolcke%
TR-91-034
Sather is an object-oriented language recently designed
and implemented at the International Computer Science
Institute in Berkeley. It compiles into C and is
intended to allow development of object-oriented,
reusable software while retaining C's efficiency and
portability. We investigate to what extent these goals
were met through a comparative performance study and
analysis of Sather and C programs on a RISC machine.
Several language design decisions in Sather are
motivated by the goal of efficient compilation to
standard architectures. We evaluate the reasoning
behind these decisions, using instruction set usage
statistics, cache simulations, and other data collected
by instrumented Sather-generated code.
We conclude that while Sather users still pay a
moderate overhead for programming convenience (in both
run time and memory usage) the overall CPU and memory
usage profiles of Sather programs are virtually
identical to those of comparable C programs. Our
analysis also shows that each of the choices made in
Sather design and implementation is well justified by a
distinctive performance advantage. It seems, then,
that Sather proves the feasibility of its own design
goal of making object-oriented programming efficient on
standard architectures using a combination of judicious
language design and efficient implementation.
-------------------------------------------------------------------------------
tr-91-035.ps.Z
HiPNeT-1 :
A Highly Pipelined Architecture for Neural Network Training
Krste Asanovic, Brian E. D. Kingsbury, Nelson Morgan,
and John Wawrzynek
TR-91-035
June 1991
Current artificial neural network (ANN) algorithms
require extensive computational resources. However,
they exhibit massive fine-grained parallelism and
require only moderate arithmetic precision. These
properties make possible custom VLSI implementations
for high performance, low cost systems. This paper
describes one such system, a special purpose digital
VLSI architecture to implement neural network training
in a speech recognition application.
The network algorithm has a number of atypical
features. These include: shared weights, sparse
activation, binary inputs, and a serial training input
stream. The architecture illustrates a number of
design techniques to exploit these algorithm-specific
features. The result is a highly pipelined system
which sustains a learning rate of one pattern per
clock cycle. At a clock rate of 20MHz each "neuron"
site performs 200 million connection updates per
second. Multiple such neurons can be integrated onto
a modestly sized VLSI die.
-------------------------------------------------------------------------------
tr-91-036.ps.Z
Experimental Determination of Precision Requirements for
Back-Propagation Training of Artificial Neural Networks
Krste Asanovic and Nelson Morgan
TR-91-036
June 1991
The impact of reduced weight and output precision on
the back-propagation training algorithm is
experimentally determined for a feed-forward
multi-layer perceptron. In contrast with previous
such studies, the network is large with over 20,000
weights, and is trained with a large, real-world data
set of over 130,000 patterns to perform a difficult
task, that of phoneme classification for a continuous
speech recognition system.
The results indicate that 16b weight values are
sufficient to achieve training and classification
results comparable to 32b floating point, provided
that weight and bias values are scaled separately, and
that rounding rather than truncation is employed to
reduce the precision of intermediary values. Output
precision can be reduced to 8 bits without significant
effects on performance.
-------------------------------------------------------------------------------
tr-91-048.ps.Z
ICSIM: An Object-Oriented Connectionist Simulator
Hienz W. Schmidt, Benedict Gomes
TR-91-048
November 1991
ICSIM is a connectionist net simulator under development
at ICSI and written in Sather. It is object-oriented
to meet the requirements for flexibility and reuse of
homogeneous and structured connectionist nets and to
allow the user to encapsulate efficient customized
implementations perhaps running on dedicated hardware.
Nets are composed by combining off-the-shelf library
classes and, if necessary, by specializing some of their
behaviour. General user interface classes allow a
uniform or customized graphic presentation of the nets
being modeled. The report gives an overview of the
simulator. Its main concepts, the class structure of
its library and some of the design decisions are
sketched and a number of example nets are used to
illustrate how net structure, interconnection and
behavior are defined.
-------------------------------------------------------------------------------
tr-91-050.ps.Z
Learning Spatial Concepts Using a Partially-Structured
Connectionist Architecture
Terry Regier
TR-91-050
October 1991
This paper reports on the learning of spatial concepts in
the L0 project. The challenge of designing an architecture
capable of learning spatial concepts from any of the world's
languages is first highlighted by reviewing the spatial
systems of a number of languages which differ strikingly
from English in this regard. A partially structured
connectionist architecture is presented which has
successfully learned concepts from the languages outlined.
In this architecture, highly structured subnetworks,
specialized for the spatial concept learning task, feed
into an unstructured, fully-connected upper subnetwork.
The system's success at the learning task is attributed on
the one hand to the constrained search space which results
from structuring, and on the other hand to the flexibility
afforded by the unstructured upper subnetwork.
-------------------------------------------------------------------------------
tr-91-058.ps.Z
Detecting Skewed Symmetries
Stefan Posch
TR-91-058
October 1991
Many surfaces of objects in our world are bounded by
planar bilaterally symmetric figures. When these figures
are imaged under orthographic projection a skewed symmetric
contour results. In this paper a new fast, local method
to recover skewed symmetries from curve segments is proposed.
It can be applied to complete as well as to occluded
contours. Furthermore, the skewed symmetry property is
employed to overcome fragmentation of a contour during
segmentation.
-------------------------------------------------------------------------------
tr-91-059.ps.Z
Line Labeling Using Markov Random Fields
Terry Regier
TR-91-059
November 1991
The task of obtaining a line labeling from a greyscale
image of trihedral objects presents difficulties not
found in the classical line labeling problem. As originally
formulated, the line labeling problem assumed that each
junction was correctly pre-classified as being of a
particular junction type (e.g. T, Y, arrow); the success
of the algorithms proposed have depended critically upon
getting this initial junction classification correct. In
real images, however, junctions of different types may
actually look quite similar, and this pre-classification
is often difficult to achieve. This issue is addressed by
recasting the line labeling problem in terms of a coupled
probabilistic system which labels both lines and junctions.
This results in a robust system, in which prior knowledge
of acceptable configurations can serve to overcome the
problem of misleading or ambiguous evidence.
-------------------------------------------------------------------------------
tr-91-061.ps.Z
Combinatory Differential Fields: An Algebraic Approach to
Approximate Computation and Constructive Analysis
Karl Aberer
TR-91-061
October 1991
The algebraic structure of combinatory differential fields
is constructed to provide a semantics for computations in
analysis. In this setting programs, approximations, limits
and operations of analysis are represented as algebraic
terms. Analytic algorithms can be derived by algebraic
methods. The main tool in this construction are combinatory
models which are inner algebras of Engeler graph models. As
an universal domain of denotational semantics the lattice
structure of the graph models allows to give a striking
simple semantics for computations with approximations. As
models of combinatory algebra they provide all essential
computational constructs, including recursion. Combinatory
models are constructed as extensions of first order theories.
The classical first order theory to describe analysis is the
theory of differential fields. It turns out that two types of
computational constructs, namely composition and piecewise
definition of functions, are preferably introduced as
extensions of the differential fields theory. Combinatory
differential fields are then the combinatory models of these
enriched differential fields. We show for basic algorithms
of computational analysis how their combinatory counterparts
are derived in the algebraic setting. We illustrate how these
algorithms are suitable to be implemented in a computer
algebra environment like mathematica.
-------------------------------------------------------------------------------
tr-91-062.ps.Z
Self-Testing/Correcting with Applications to Numerical Problems
(Revised Version)}
Manuel Blum, Michael Luby, Ronitt Rubinfeld
TR-91-062
Suppose someone gives us an extremely fast program $P$
that we can call as a black box to compute a function $f$.
Should we trust that $P$ works correctly?
A {\em self-testing/correcting pair} for $f$ allows us to:
(1) estimate the probability that $P(x) \not= f(x)$ when $x$ is
randomly chosen; (2) on {\em any} input $x$, compute $f(x)$
correctly as long as $P$ is not too faulty on average.
Furthermore, both (1) and (2) take time only slightly more
than the original running time of $P$.
We present general techniques for constructing simple to
program self-testing/\-correcting pairs for a variety of
numerical functions, including integer multiplication,
modular multiplication, matrix multiplication,
inverting matrices, computing the determinant
of a matrix, computing the rank of a matrix, integer division,
modular exponentiation and polynomial multiplication.
-------------------------------------------------------------------------------
tr-91-064.ps.Z
Distortion Accumulation in Image Transform Coding/Decoding Cascades
Michael Gilge
TR-91-064
December 1991
With an increasing number of applications that employ
transform coding algorithms for data reduction, the effect
of distortion accumulation caused by multiple coding needs
to be investigated. Multiple coding occurs when more than
one coding system is connected in a cascade. From the
second stage on, the coding algorithm operates on data that
has been previously coded/decoded. First a generic image
communication system is being modelled and situations that
can lead to distortion accumulation are analyzed. These
results show two main reasons for distortion accumulation,
which are separately and jointly investigated using a
JPEG-type compression algorithm. The first situation
involves geometric operations between the decoding and next
coding step. Measurements show however that these spatial
manipulations are the main contributors to distortion
accumulation. The second reason for distortion accumulation
is a misalignment of the block segmentation reference point
in subsequent transform operations. A block raster
detection algorithm is derived that can find the position
of the block raster that was introduced in a previous
coding step. If this information is used in the block
segmentation of the following coding step, distortion
accumulation can be avoided. Simulation results are given
for an extended algorithm that registers regions of
homogeneous block raster in images consisting of several
subimages.
-------------------------------------------------------------------------------
tr-91-065.ps.Z
Motion Video Coding for Packet-Switching Networks
-- An Integrated Approach
Michael Gilge and Riccardo Gusella
TR-91-065
December 1991
The advantages of packet video, constant image quality,
service integration and statistical multiplexing, are
overshadowed by packet loss, delay and jitter. By
integrating network-control into the image data
compression algorithm, the strong interactions between the
coder and the network can be exploited and the available
network bandwidth can be used best. In order to enable
video transmission over today's networks without
reservation or priorities and in the presence of high
packet loss rates, congestion avoidance techniques need to
be employed. This is achieved through rate and flow
control, where feedback from the network is used to adapt
coding parameters and vary the output rate. From the
coding point of view the network is seen as data buffer.
Analogously to constant bit rate applications, where a
controller measures buffer fullness, we attempt to avoid
network congestion (eq. buffer overflow) by monitoring the
network and adapting the coding parameters in real-time.
-------------------------------------------------------------------------------
tr-91-068.ps.Z
Construction of a pseudo-random generator from any one-way function
Johan Hastad, Russell Impagliazzo, Leonid A. Levin, Michael Luby
TR-91-068
We show how to construct a pseudo-random generator
from any one-way function. In contrast, previous works
have constructed pseudo-random generators only
from one-way functions with special structural properties.
Our overall approach is different in spirit from previous work;
we concentrate on extracting and smoothing entropy from
a single iteration of the one-way function using
universal hash functions.
-------------------------------------------------------------------------------
tr-91-069.ps.Z
RASTA-PLP Speech Analysis
Hynek Hermansky, Nelson Morgan, Aruna Bayya, and Phil Kohn
TR-91-069
December 1991
Most speech parameter estimation techniques are easily
influenced by the frequency response of the communication
channel. We have developed a technique that is more robust
to such steady-state spectral factors in speech. The
approach is conceptually simple and computationally efficient.
The new method is described, and experimental results are
reported, showing a significant advantage for the proposed
method.
-------------------------------------------------------------------------------
tr-91-070.ps.Z
Connectionist Speech Recognition: Status and Prospects
Steve Renals, Nelson Morgan, Herve Bourlard, Michael Cohen,
Horacio Franco, Chuck Wooters and Phil Kohn.
TR-91-070
December 1991
We report on recent advances in the ICSI connectionist
speech recognition project.
Highlights include:
1. Experimental results showing that connectionist
methods can improve the performance of a context
independent maximum likelihood trained HMM system,
resulting in a performance close to that achieved
using state of the art context dependent HMM systems
of much higher complexity;
2. Mixing (context independent) connectionist
probability estimates with maximum likelihood trained
context dependent models to improve the performance of
a state of the art system;
3. The development of a network decomposition method
that allows connectionist modelling of context
dependent phones efficiently and parsimoniously, with
no statistical independence assumptions.
-------------------------------------------------------------------------------
tr-91-071.ps.Z
GDNN: A Gender-Dependent Neural Network
for
Continuous Speech Recognition
Yochai Konig, Nelson Morgan, and Claudia Chandra
TR-91-071
December 1991
Conventional speaker-independent speech recognition systems do not
consider speaker-dependent parameters in the probability estimation
of phonemes. These recognition systems are
instead tuned to the ensemble statistics over many speakers.
Most parametric representations of speech, however, are highly
speaker dependent, and probability distributions suitable for
a certain speaker may not perform as well for other speakers.
It would be desirable to incorporate
constraints on analysis that rely on the same speaker producing
all the frames in an utterance. Our experiments take a first step
towards this speaker consistency modeling by using a
classification network to help generate gender-dependent
phonetic probabilities for a statistical recognition system.
Our results show a good classification rate for the gender
classification net. Simple use of such a model to augment
an existing larger network that estimates phonetic
probabilities does not help speech recognition performance.
However, when the new net is properly integrated in an HMM
recognizer, it provides significant improvement in word accuracy.
-------------------------------------------------------------------------------
tr-91-072.ps.Z
SPERT: A VLIW/SIMD Microprocessor for
Artificial Neural Network Computations
Krste Asanovic, James Beck, Brian E. D. Kingsbury, Phil Kohn,
Nelson Morgan, John Wawrzynek
TR-91-072
December 1991
SPERT (Synthetic PERceptron Testbed) is a fully programmable single
chip microprocessor designed for efficient execution of artificial
neural network algorithms. The first implementation will be in a
1.2 micron CMOS technology with a 50MHz clock rate, and a prototype
system is being designed to occupy a double SBus slot within a Sun
Sparcstation.
SPERT will sustain over 300 million connections per second during
pattern classification, and around 100 million connection updates
per second while running the popular error backpropagation training
algorithm. This represents a speedup of around two orders of magnitude
over a Sparcstation-2 for algorithms of interest. An earlier system
produced by our group, the Ring Array Processor (RAP), used commercial
DSP chips. Compared with a RAP multiprocessor of similar performance,
SPERT represents over an order of magnitude reduction in cost for
problems where fixed-point arithmetic is satisfactory.
This report describes the current architecture, and gives the
results of detailed simulations. The report also makes a short
comparison to other high-performance digital neurocomputing chips.
-------------------------------------------------------------------------------
tr-91-074.ps.Z
Recent Work in VLSI Elements for Digital Implementations of
Artificial Neural Networks
Brian E. D. Kingsbury, Bertrand Irissou, Krste Asanovic,
John Wawrzynek, Nelson Morgan
TR-91-074
December 1991
A family of high-performance, area-efficient VLSI elements is
being developed to simplify the design of artificial neural
network processors. The libraries are designed around the
MOSIS Scalable CMOS design rules, giving users the option of
fabricating designs in 2.0um or 1.2um n-well processes, and
greatly simplifying migration of the libraries to new MOSIS
technologies. To date, libraries and generators have been
created for saturating and nonsaturating adders, a
two's-complement multiplier, and a triple-ported register
file. The SPERT processor currently being designed at ICSI
will be based upon these libraries, and is expected to run at
50 MHz when realized in a 1.2um CMOS technology.
-------------------------------------------------------------------------------
tr-92-005.ps.Z
New algorithmic results for lines-in-3-space problems
Leonidas J. Guibas and Marco Pellegrini
TR-92-005
January 1992
In the first part of the report we consider some incidence and ordering
problems for lines in 3-space. We solve the problem of detecting
efficiently if a query simplex is collision-free among polyhedral
obstacles. In order to solve this problem we develop new on-line data
structures to detect intersections of query halfplanes with
sets of lines and segments.
Then, we consider the nearest-neighbor problems for lines.
Given a set of$n$ lines in 3-space, the shortest vertical segment between
any pair of lines is found in randomized expected time
$O(n^{8/5+\epsilon})$ for every $\eps>0$.
The longest connecting vertical segment is found in time $O(n^{4/3+\eps})$.
The shortest connecting segment is found in time $O(n^{5/3 + \epsilon})$.
Problems involving lines, points and spheres in 3-space have important
applications in graphics, CAD and optimization.
In the second part of the report we consider several problems of this kind.
We give subquaratic algorithms to count the number of incidences
between a set of lines and a set of spheres, and to find the minimum
distance between a set of lines and a set of points.
We show that the sphere of minimum radius intersecting every line in
a set of $n$ lines can be found in optimal expected time $O(n)$.
Given $m$ possibly intersecting spheres we solve ray-shooting queries
in $O(\log^2 m)$ time using a data structure of size $O(m^{5+\eps})$.
This technical report collects part of the second author's work
at I.C.S.I. form September 1991 to January 1992.
-------------------------------------------------------------------------------